COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00008 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A71.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 7, 1988}
\leftline{\sevenrm Unpublished Draft}
\bigskip
\noindent{\bf Definitions of Acceptance, Recognition, and Simulation}
\def\rtau{\mathrel{\tau}}

If $M$ is a machine, $P$ a program for $M$, and $x$ an argument of $P$, we
say $P$ {\it accepts\/} $x$ if there is a computation of $P$ on $M$ with
argument $x$ that ends in an accepting control state, that is if $x
\rtau↓p\hbox {TRUE}$.  We say $P$ {\it rejects\/} $x$ if there is a
computation of $P$ on $x$ that ends in a rejecting control state; that is, if
$x \rtau↓p\hbox {FALSE}$.

If $L$ is a set of arguments for $P$ (called a {\it language\/} if
arguments are strings), to say $P$ {\it accepts\/} $L$ means
$(\hbox{$P$ accepts $x$}) ≡ (x \in L)$; $P$ accepts the elements of $L$ and
nothing else.  Notice that ``$P$ accepts $\{x\}$'' is a much stronger
statement than ``$P$ accepts $x$''.

To say $P$ {\it recognizes\/} $L$ means that $P$ is deterministic, halts on
all arguments, accepts the members of $L$, and rejects the non-members of
$L$.  By making the accepting control states of $P$ rejecting and vice
versa, we get a program $\bar P$ that recognizes $\bar L$.  It is shown
elsewhere that a standardized DPDA recognizes the language it accepts, so
the complementary language is also recognized by a DPDA.

If $C$ is a class of languages, to say $M$ {\it accepts\/} $C$ means
(Some program for $M$ accepts $L$) if and only if $(L\in C)$;
programs for $M$ accept the elements of $C$ and nothing else.  For
example, if $C$ is the set of context-free languages (those definable in
BNF notation), $M$ the pushdown acceptor, $M$ accepts $C$; every program
accepts a language definable in BNF, and every language definable in BNF
has a NPDA.

If $C$ is a class of languages, to say $M$ {\it recognizes\/} $C$ means
(Some program for $M$ recognizes $L$) if and only if $(L \in C)$.  
If $M$ is the
PDA, the languages of the class $M$ recognizes are called the
deterministic pushdown languages; they are a proper subset of the
context-free languages.  If $M$ is a Turing machine, sets accepted by $M$
are called {\it recursively enumerable\/}; sets recognized by $M$ are
called {\it recursive}.

We say that program $P'$ {\it simulates\/} program $P$ if the sufficient conditions
hold (defined elsewhere) that guarantee $\rtau↓p \subseteq \rtau↓{p'}$.  If
$\hbox {dom}\, \rtau↓{p'} \subseteq \hbox {dom}\, \rtau↓p$ (particularly, if
$\rtau↓p$ is a total relation) and $\rtau↓{p'}$ is a partial function, then
$\rtau↓p = \rtau↓{p'}$.  Otherwise, to prove $\rtau↓p = \rtau↓{p'}$ one can prove
{\it mutual simulation\/}: each simulates the other.

We say that machine $M'$ {\it simulates\/} machine $M$ if for every program
$P$ of $M$, there is a program $P'$ of $M'$ with the same transfer
relation; for example, $P$ and $P'$ might mutually simulate each other as
define above.

We say that device $d'$ simulates device $d$ if $d$, occurring in any
machine $M$, can be repaced by $d'$ to give a machine, $M'$, that
simulates $M$.  It appears to be true that if $M' = \langle\hbox{control},
\hbox{input}, d, \hbox {output}\rangle$ simulates $M =
\langle\hbox{control}, \hbox{input}, d', \hbox{output}\rangle$, then $d'$
simulates $d$ in any other context.  (But I haven't actually seen this
demonstrated.)

\bye